package leetcode.editor.cn.q1_300.q50;

/**
 * @author qidi
 * @date 2021-12-09 10:02:50
 */
class Q0052_NQueensIi {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int totalNQueens(int n) {
            int[] arr = new int[n];
            return process(n, 0, arr);
        }

        private int process(int n, int i, int[] arr) {
            if (i == n) return 1;

            int res = 0;
            for (int j = 0; j < n; j++) {
                if (check(arr, i, j)) {
                    arr[i] = j;
                    res += process(n, i + 1, arr);
                }
            }

            return res;
        }

        private boolean check(int[] arr, int i, int j) {
            for (int k = 0; k < i; k++) {
                if (arr[k] == j || Math.abs(arr[k] - j) == Math.abs(i - k)) return false;
            }
            return true;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0052_NQueensIi().new Solution();
        System.out.println(solution.totalNQueens(4));
    }
}